package org.xingole.leetcode.dp;

/**
 * 
 * <a href="https://leetcode.com/problems/palindromic-substrings/description/">
 * Problem Description
 * </a>
 * 
 * A string is a palindrome when it reads the same backward as forward.
 * A substring is a contiguous sequence of characters within the string.
 */
public class PalindromicSubstrings {
    /**
     * Given a string s, return the number of palindromic substrings in it.
     * 
     * <p>
     * <strong>Complexity Analysis</strong>
     * <ul>
     *      <li>Time Complexity: O(n^2)
     *      <li>Space Compelxity: O(1)
     * </ul>
     */
    public int countSubstrings(String s) {
        int n   = s.length();
        int ans = 0;

        for (int i = 0; i < 2 * n - 1; i++) {
            int li = i / 2;
            int ri = i / 2 + i % 2;

            while (li >= 0 && ri < n && s.charAt(li) == s.charAt(ri)) {
                --li;
                ++ri;
                ++ans;
            }
        }

        return ans;
    }

    public int countSubstringsWithManacher(String s) {
        int n = s.length();
        StringBuffer t = new StringBuffer("$#");
        for (int i = 0; i < n; i++) {
            t.append(s.charAt(i));
            t.append('#');
        }
        n = t.length();
        t.append('!');

        // We use f[i] to represent the maximum palindrome radius
        // that can be extended with the ith position of s as the 
        // palindrome center. Then, f[i]-1 is the maximum length of
        // the palindrome string centered on i.
        int[] f = new int[n];

        // The Manacher algorithm requires us to maintain the right
        // endpoint rMax of the current largest palindrome and the
        // palindrome center iMax corresponding to this palindrome
        // right endpoint.
        int iMax = 0, rMax = 0;
        int ans  = 0;

        // The Manacher algorithm still needs to enumerate every
        // position of s and first assume it to be the palindrome
        // center, but it will update f[i] using the already calculated
        // state.
        for (int i = 1; i < n; i++) {
            // 1. Initilize f[i]:
            // - If i <= rMax, it indicates that i is included in the current
            // largest palindrome substring. Suppose j is the symmetric
            // position of i with respect to the palindrome center iMax (that is
            // j + i = 2*iMax), we can get that f[i] is at least equal to
            // min{f[j], rMax - i + 1}.
            f[i] = i <= rMax ? Math.min(rMax - i + 1, f[2 * iMax - i]) : 1;

            // 2. Central Expansion
            while (t.charAt(i + f[i]) == t.charAt(i - f[i])) {
                ++f[i];
            }

            if (i + f[i] - 1 > rMax) {
                iMax = i;
                rMax = i + f[i] - 1;
            }

            ans += f[i] / 2;
        }

        return ans;
    }
}
